package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.回溯;

import java.util.*;

/**
 * @author By ZengPeng
 */
public class 力扣_90_子集II {
    //测试
    public static void main(String[] args) {

        System.out.println(new 力扣_90_子集II().subsetsWithDup(new int[]{1,2,2}));
        System.out.println(new 力扣_90_子集II().subsetsWithDup(new int[]{0}));
    }

    /**
    题目：给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
          解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

     示例 1：
     输入：nums = [1,2,2]
     输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
     示例 2：

     输入：nums = [0]
     输出：[[],[0]]

    分析：【P ❤🧡💛】
       1.回溯法: 这里要注意内容相同的情况
               注意：记录每个节点的使用情况.
               难点：isUsed[j-1 == false 表示:前面的相同值未被使用过，说明当前值是开头，结果已经被前面的值遍历过了，我们直接跳过
               --执行用时：1 ms, 在所有 Java 提交中击败了98.98%的用户
     边界值 & 注意点：
       1.
     **/
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        Arrays.sort(nums);
        Deque<Integer> deque = new ArrayDeque<>();
        boolean[] isUsed = new boolean[nums.length];
        reverse(nums,isUsed,0,deque,res);
        return res;
    }

    private void reverse(int[] nums,boolean[] isUsed , int index,Deque<Integer> deque, List<List<Integer>> res) {
        for (int j = index; j < nums.length; j++) {
            if(j>0 && nums[j]==nums[j-1]&&!isUsed[j-1]) continue;//isUsed[j-1 == false 表示:前面的相同值未被使用过，说明当前值是开头，结果已经被前面的值遍历过了，我们直接跳过
            deque.addLast(nums[j]);
            isUsed[j] =true;
            res.add(new ArrayList<>(deque));
            reverse(nums,isUsed,j+1,deque,res);
            deque.removeLast();
            isUsed[j] =false;
        }
    }
}
